The present invention relates to an ACS unit (Add Compare Select) as claimed in the preamble of claim 1 for a Viterbi decoder, which can be used in particular in mobile radio receivers for decoding channel-coded mobile radio signals.
A Viterbi decoder is used in most known digital mobile radio receivers. A Viterbi decoder is what is referred to as a maximum likelihood decoder, which is generally used for decoding channel-coded, in particular convolution-coded, mobile radio signals. During the channel coding process, redundant information is added in the transmitter to the symbols to be transmitted, in order to increase the transmission reliability. However, when a mobile radio signal is transmitted, noise is superimposed on it. The object of the receiver is thus to use the received sequence to find from all the possible transmission sequences that transmission sequence which most probably corresponds to the actual transmission sequence. This object is carried out by the Viterbi decoder.
The coding rule used for channel coding can be described by a corresponding trellis diagram. The Viterbi decoder calculates what are referred to as metrics to determine that path in the trellis diagram which has greatest or smallest path metric depending on the respective configuration of the decoder. The decoded sequence can then be determined and emitted, on the basis of this path in the trellis diagram.
The principles of Viterbi decoding will be explained in more detail, briefly, in the following text.
By way of example, FIG. 4 shows a trellis diagram in each case having four different states at the times t . . . t+3, which correspond, for example, to the bit states xe2x80x9800xe2x80x99, xe2x80x9810xe2x80x99, xe2x80x9801xe2x80x99 and xe2x80x9811xe2x80x99. Each symbol sequence is allocated a corresponding path in the trellis diagram. A path in this case comprises a sequence of branches between two successive states in time. Each branch in this case symbolizes a state transition between two successive states in time, with, for example, the upper branch originating from one state corresponding to a received symbol with the binary value xe2x80x980xe2x80x99, and the lower branch originating from the same state corresponding to a received symbol with the binary value xe2x80x981xe2x80x99. Each of these state transitions, to which a branch metric (BM) xcext is assigned, corresponds to a transmitted symbol. The branch metric xcext is defined as follows:
xcex1=|yxe2x80x21xe2x88x92r12|
In this case, rt corresponds to the received symbol at the time t, and yxe2x80x2t corresponds to the expected transmitted symbol, as a function of this, at the time t.
Furthermore, each path through the trellis diagram is assigned a path metric xcex3t until the time or time step t.
The trellis diagram illustrated in FIG. 4 is, in particular, a trellis diagram with what is referred to as a butterfly structure. This means that two states of a time step t+1 in the trellis diagram are in each case assigned two states from the previous time step t, whose branches each lead to the first-mentioned states in the time step t+1, with two branch metrics of the branches originating from different states in each case being identical. Thus, for example, the states shown in FIG. 4, to which the path metrics xcex3t(1), xcex3t(3), xcex3txe2x88x921(2) and xcex3t+1(3) are assigned, form such a butterfly structure, with the branch metric for the branch from the state with the path metric xcex3t(1) to the state with the path metric xcex3t+1(2) corresponding to the branch metric xcext(3) of the branch from the state with the path metric xcex3t(3) to the state with the path metric xcex3txe2x88x921(3) while, on the other hand, the branch metric of the branch from the state with the path metric xcex3t(1) to the state with the path metric xcex3t+1(3) corresponds to the branch metric xcext(1) of the branch from the state with the path metric xcex3t(3) to the state with the path metric xcex3t+1(2). In this case, in general form, xcex3t(s) denote the path metric assigned to the state s in the time step t, while xcex3t(S) denotes the branch metric of the state transition, corresponding to the signal s, at the time t.
The Viterbi decoder now has to use the trellis diagram to determine that path which has the best path metric. In general, by definition, this is the path with the smallest path metric.
Each path metric of a path leading to a specific state is composed of the path metric of a previous state in time and of the branch metric of the branch leading from this previous state to the specific state. This means that there is no need to determine and evaluate all the possible paths and path metrics in the trellis diagram. Instead of this, that path which has the best path metric up to this time is determined for each state and for each time step in the trellis diagram only this path, which is referred to as the survivor path, and its path metric need be stored. All the other paths which lead to this state can be ignored. Accordingly, during each time step, there are a number of such survivor paths corresponding to the number of different states.
The above description makes it clear that the calculation of the path metric xcex3t+1(s) depends on the path metrics of the path metrics of the previous time step t connected to the state s via one branch. The path metrics can accordingly be calculated by means of a recursive algorithm, which is carried out by what is referred to as an Add Compare Select unit (ACS unit) in a Viterbi decoder.
FIG. 5 shows the typical configuration of a Viterbi decoder. In addition to the ACS unit, the Viterbi decoder has a branch metric unit (BMU) and a survivor memory unit. The object of the branch metric unit is to calculate the branch metrics xcex3t(s), which are a measure of the difference between a received symbol and that symbol which causes the corresponding state transition in the trellis diagram. The branch metrics calculated by the branch metric unit are supplied to the ACS unit in order to determine the optimum paths (survivor paths), with the survivor memory unit storing these survivor paths so that, in the end, decoding can be carried out on the basis of that survivor path which has the best path metric. The symbol sequence associated with this path has the highest probability of corresponding with the actually transmitted sequence.
A processor element 1 in a conventional ACS unit can be designed as shown by way of example in FIG. 6. In this case, it is assumed that each state in the trellis diagram is evaluated by a separate processor element 1. The task of the processor element 1 is to select from two mutually competing paths which lead to one state in the trellis diagram that path which has the best, that is to say lowest, path metric. The stored values for the survivor path leading to this state, and its path metric, are then updated.
As can be seen from the trellis diagram shown in FIG. 4, each state s at the time t+1 is connected via an upper branch and a lower branch to a corresponding previous state. In order to determine the survivor path corresponding to this state s, the path metric of the path leading via the upper branch to the state s must therefore be compared with the path metric of the path leading via the lower branch to the state s, that is to say the task of the processor element 1 shown in FIG. 6, in order to determine the survivor path with the path metric xcex3t+1(s) is to select either the path which leads via the previous xe2x80x98upperxe2x80x99 state with the path metric xcex3t(0) and the xe2x80x98upperxe2x80x99 branch with the path metric xcext(0) and whose path metric corresponds to the sum xcex3t(0)+xcext(0) or the path which leads via the lower state with the path metric xcex3t(1) and the lower branch with the branch metric xcext(1) and whose path metric corresponds to the sum xcex3t(1)+xcext(1).
The operation of the processor element described above can in consequence be carried out, for example, by the circuit shown in FIG. 6, in which the possible path metrics are calculated by means of adders 14 and 15 and are compared by means of a comparator 16, so that, depending on the comparison result xcex4s, the smaller of the sums calculated by the two adders 14 or 15 can then be emitted, with the aid of the multiplexer 17, as the path metric xcex3txe2x88x921(s).
FIG. 7 shows the overall configuration and the connection of an ACS unit to the branch metric unit and to the survivor memory unit, for the trellis diagram shown by way of example in FIG. 4. Since each result xcex3t(s) which is calculated for a state s in the time step t at the same time forms the basis for the calculation of a path metric for a successive state in time, the feedback of the processor element 1, as shown in FIG. 7, via an intermediate register 18 is required. The decision or signal values xcex40 . . . xcex43 supplied from the individual processor elements 1 to the survivor path unit allow the selection and storage of the correct survivor paths, and of their path metrics.
The already described ACS unit is the most computationally intensive part of a Viterbi decoder. This occupies the greatest surface area and has the highest power requirement. For applications in mobile radio technology, the complexity of the ACS unit in this case rises exponentially with the complexity of the respective code used for channel coding of mobile radio signals.
There is thus a fundamental requirement to keep the circuit complexity for the ACS unit as simple as possible. It has therefore been proposed, for example in the document xe2x80x9cLow Power ACS Unit Design For The Viterbi Decoderxe2x80x9d, Chi-ying Tsui, Roger S. K. Cheng, Curtis Ling, Conference IEEE ISCAS, 1999, Orlando, which describes an ACS unit as claimed in the preamble of claim 1, for determining a survivor path of a state, to form the difference between the path metrics for those previous states from each of which one branch leads to the state under consideration, and to compare this with the difference between the corresponding branch metrics. Depending on the comparison result, it is thus possible to directly deduce the survivor path, and hence the sum that needs to be formed to calculate the corresponding path metric. This procedure has the advantage that, assuming the already mentioned butterfly structure, the differences can be worked out jointly for the calculation of the path metrics from two states in one time step in the trellis diagram, which means that the circuit complexity can be reduced.
However, this procedure still also requires the separate formation of a comparison for determining the path metrics of the upper and lower states of a time step associated with the respective butterfly structure, with two comparators correspondingly being required for this purpose.
U.S. Pat. No. 5,781,569 discloses an ASC unit which comprises an adder for supplying the magnitude and the mathematical sign of a difference of state weights and path metrics at a time t, a further adder for supplying the magnitude and the mathematical sign of a difference of branch metrics, a comparator which compares the magnitudes of the differences and supplies a signal which indicates which difference is the greater, and a control logic device, which uses the mathematical signs and the signal from the comparator to determine which state weights and metrics are used in order to determine the weights of states at a time t+1 using still further adders.
The article by Page et al. xe2x80x9cImproved Architectures for the Add-Compare-Select Operation in Long Constraint Length Viterbi Decodingxe2x80x9d, IEEE 1998 (XP66629) discloses a decoupled architecture for ACS units, which is optimized such that the buffer storage requirements in the form of registers for ACS units and with a large number of output state metrics and path metrics are reduced.
U.S. Pat. No. 5,815,515 discloses two specialized butterfly calculation units, which are each used as a function of edge metric values for edges which connect the states in a Viterbi decoder to calculate path weights for a time t+1 from path weights for a preceding time t.
Against the background of this prior art, the present invention is therefore based on the object of providing an ACS unit for a Viterbi decoder with less complex circuitry and occupying less surface area.
According to the invention, this object is achieved by an ACS unit having the features of claim 1. The dependent claims define advantageous and preferred embodiments of the present invention.
According to the invention, assuming the already described butterfly structure of the trellis diagram, the path metrics from two states of a time step in the trellis diagram are calculated as a function of a comparison between the difference of the path metrics of those states which are connected to these states via the butterfly structure in the immediately preceding time slot in the trellis diagram, and the difference between the corresponding branch metrics, with the mathematical signs of the path metric difference and of the branch metric difference also being calculated.
This procedure results in a considerable reduction in the circuitry complexity of the ACS unit. Investigations have shown that the computation complexity can be reduced by about 33% by means of the present invention for all codes currently used in digital communications technology (mobile radio technology (for example in accordance with the GSM or UMTS mobile radio standard), satellite communication, and wire-free communication in general). A corresponding power saving is thus also possible, in comparison to the known prior art. In particular, in comparison to the ACS unit proposed in the document xe2x80x9cLow Power ACS Unit Design For the Viterbi Decoderxe2x80x9d, Chi-ying Tsui, Roger S. K. Cheng, Curtis Ling, Conference IEEE ISCAS, 1999, Orlanda, there is no need for a separate comparator for determining the path metrics of the upper and lower state of the butterfly structure. The comparison to be formed in the ACS unit according to the invention between the path metric difference described above and the branch metric difference can be carried out with a small number of bits, which likewise contributes to a saving in the circuit surface area and power required.
The ACS unit according to the invention can be produced using simple means, both in the form of a combinational circuit as well as in the form of a sequential circuit. The surface area required for the ACS unit is reduced in particular since two trellis states can be processed simultaneously by means of the present invention. All the states in one time step of the respectively used trellis diagram can be processed either completely in parallel (if the number of processor elements in the ACS unit corresponds at least to half the number of states in a time step) or by time-division multiplexing (if the number of processor elements is less).
According to one preferred embodiment of the present invention, an input comparator can also be provided, which compares specific bits in the path metric difference and branch metric difference with one another, with the comparison result also being evaluated in order to make it possible where possible even at an early stage, to determine the components that need to be added to calculate the path metrics, without needing to activate the actual comparator for this purpose. If a two""s complement representation is used, it is thus possible, for example, to determine the ratio of the mathematical signs in the path metric difference and the branch metric difference by comparing the most significant bits.